//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================
#include "ddk.h"

#include <stdio.h>
#include <stdlib.h>

#include <misc.h>
#include <hash.h>

extern int PageNeeded(int size);
/*
 * hashval()
 *    Convert key into hash value
 */
static inline UInt32 hashidx(UInt32 key, UInt32 mask)
{
    return((key ^ (key >> 2) ^ (key >> 6)) & mask);
}

/*
 * hash_alloc()
 *    Allocate a hash data structure of the given hash size
 *
 * For speed we always round the hash table size to the nearest power
 * of 2 above the requested size.
 */
EXTERN_C struct hash *hash_alloc(int hashsize)
{
    struct hash *h = NULL;
    int i = 3, hashlim = 8;

    /*
     * Adjust hash size to the next power of 2
     */
    while (hashsize > hashlim) {
        i++;
        hashlim <<= 1;
    }
    h = (struct hash *)malloc(sizeof(struct hash) + hashlim * sizeof(struct hash *));
    if (h) {
        h->h_hashsize = hashlim;
        h->h_hashmask = hashlim - 1;
        bzero(&h->h_hash, hashlim * sizeof(struct hash *));
        Ktfs_Init_Lock(&h->h_lock);
    }
    return h;
}

/*
 * hash_insert()
 *    Insert a new key/value pair into the hash
 *
 * Returns TRUE on error, FALSE on success.
 */
EXTERN_C Boolean hash_insert(struct hash *h, long key, void *val)
{
    struct hash_node *hn = NULL;
    UInt32 idx;

    if (!h) {
        return TRUE;
    }
    Ktfs_Lock(&h->h_lock);
    idx = hashidx(key, h->h_hashmask);
    hn = (struct hash_node *)malloc(sizeof(struct hash_node));
    if (!hn) {
        Ktfs_Unlock(&h->h_lock);
        return TRUE;
    }
    hn->h_key = key;
    hn->h_data = val;
    hn->h_next = h->h_hash[idx];
    h->h_hash[idx] = hn;
    Ktfs_Unlock(&h->h_lock);
    return FALSE;
}

/*
 * hash_delete()
 *    Remove node from hash
 *
 * Returns TRUE if key not found, FALSE if removed successfully.
 */
EXTERN_C Boolean hash_delete(struct hash *h, long key)
{
    struct hash_node **hnp, *hn;
    UInt32 idx;

    if (!h) {
        return TRUE;
    }
    Ktfs_Lock(&h->h_lock);
    /*
     * Walk hash chain list.  Walk both the pointer, as
     * well as a pointer to the previous pointer.  When
     * we find the node, patch out the current node and
     * free it.
     */
    idx = hashidx(key, h->h_hashmask);
    hnp = &h->h_hash[idx];
    hn = *hnp;
    while (hn) {
        if (hn->h_key == key) {
            *hnp = hn->h_next;
            free(hn);
            Ktfs_Unlock(&h->h_lock);
            return FALSE;
        }
        hnp = &hn->h_next;
        hn = *hnp;
    }
    Ktfs_Unlock(&h->h_lock);
    return TRUE;
}

/*
 * hash_dealloc()
 *    Free up the entire hash structure
 */
EXTERN_C Void hash_dealloc(struct hash *h)
{
    UInt32 x;
    struct hash_node *hn = NULL, *hnn = NULL;
    Ktfs_Lock(&h->h_lock);
    for (x = 0; x < (UInt32)h->h_hashsize;++x) {
        for (hn = h->h_hash[x]; hn; hn = hnn) {
            hnn = hn->h_next;
            free(hn);
        }
    }
    Ktfs_Unlock(&h->h_lock);
    Ktfs_Term_Lock(&h->h_lock);
    free(h);
}

/*
 * hash_lookup()
 *    Look up a node based on its key
 */
EXTERN_C PVoid hash_lookup(struct hash *h, long key)
{
    struct hash_node *hn = NULL;
    UInt32 idx;
    if (!h) {
        return NULL;
    }
    Ktfs_Lock(&h->h_lock);
    idx = hashidx(key, h->h_hashmask);
    for (hn = h->h_hash[idx]; hn; hn = hn->h_next) {
        if (hn->h_key == key) {
            Ktfs_Unlock(&h->h_lock);
            return(hn->h_data);
        }
    }
    Ktfs_Unlock(&h->h_lock);
    return NULL;
}

/*
 * hash_size()
 *    Tell how many elements are stored in the hash
 */
EXTERN_C UInt32 hash_size(struct hash *h)
{
    UInt32 x, cnt = 0;
    struct hash_node *hn;
    Ktfs_Lock(&h->h_lock);
    for (x = 0; x < (UInt32) h->h_hashsize;++x) {
        for (hn = h->h_hash[x]; hn; hn = hn->h_next) {
            cnt += 1;
        }
    }
    Ktfs_Unlock(&h->h_lock);
    return cnt;
}

/*
 * hash_foreach()
 *    Enumerate each entry in the hash, invoking a function
 */
EXTERN_C Void hash_foreach(struct hash *h, intfun f, void *arg)
{
    UInt32 x;
    struct hash_node *hn = NULL;
    Ktfs_Lock(&h->h_lock);
    for (x = 0; x < (UInt32)h->h_hashsize;++x) {
        for (hn = h->h_hash[x]; hn; hn = hn->h_next) {
            if ((*f)(hn->h_key, hn->h_data, arg)) {
                Ktfs_Unlock(&h->h_lock);
                return;
            }
        }
    }
    Ktfs_Unlock(&h->h_lock);
}
